#include "abb.h"
#include "pila.h"

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

/* ******************************************************************
 *                IMPLEMENTACION DE LOS TIPOS DE DATOS
 * *****************************************************************/

typedef struct abb_nodo {
	char *clave;
	void *dato;
	struct abb_nodo *izq;
	struct abb_nodo *der;
} abb_nodo_t;

struct abb {
	abb_nodo_t *raiz;
	abb_comparar_clave_t cmp;
	abb_destruir_dato_t destruir_dato;
	size_t cantidad;
};

struct abb_iter{
	const abb_t *arbol;
	pila_t *pila;
	abb_nodo_t *actual;
};

/*******************************************************************
 *              IMPLEMENTACION PRIMITIVAS DEL ABB
 ******************************************************************/

// Copia la cadena pasada por parametro.
// Pre: la cadena fue creada.
// Post: Devuelve la copia de la cadena o NULL en caso de error.
char *obtener_copia_cadena(const char *cadena){
	char *copia_cadena = malloc((strlen(cadena)+1)*sizeof(char));
	if (!copia_cadena) return NULL;
	return strcpy(copia_cadena, cadena);
}

abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato){
	abb_t *abb = malloc(sizeof(abb_t));
	if (!abb)
		return NULL;

	abb->raiz = NULL;
	abb->cmp = cmp;
	abb->destruir_dato = destruir_dato;
	abb->cantidad = 0;
	return abb;
}

// Crea un nodo de abb.
// Post: devuelve NULL si no se pudo crear el nodo del abb,
// en caso contrario devuelve un nuevo nodo de abb vacío.
abb_nodo_t *abb_nodo_crear(const char *clave, void *dato){
	abb_nodo_t *abb_nodo = malloc(sizeof(abb_nodo_t));
	if (!abb_nodo)
		return NULL;

	char *copia_cadena = obtener_copia_cadena(clave);
	if(!copia_cadena){
		free(abb_nodo);
		return NULL;
	}

	abb_nodo->clave = copia_cadena;
	abb_nodo->dato = dato;

	abb_nodo->der = NULL;
	abb_nodo->izq = NULL;

	return abb_nodo;
}

// Destruye el nodo del arbol.
// Pre: el nodo fue creado.
// Post: se libero toda la memoria ocupada por el nodo. No devuelve nada.
void abb_nodo_destruir(abb_nodo_t *nodo, abb_destruir_dato_t destruir_dato){
	free(nodo->clave);
	if (destruir_dato != NULL)
		destruir_dato(nodo->dato);
	free(nodo);
}

// Devuelve el puntero al abb_nodo que contiene la clave, en caso que la clave no pertenezca
// devuelve un puntero a NULL.
// Pre: el arbol, la clave y el nodo fueron creados.
abb_nodo_t **obtener_puntero_abb_nodo(const abb_t* arbol, const char* clave, abb_nodo_t* const* nodo){
	if ((*nodo) == NULL)
		return (abb_nodo_t **) nodo;

	if (arbol->cmp(clave, (*nodo)->clave) == 0)
		return (abb_nodo_t **) nodo;

	if (arbol->cmp(clave, (*nodo)->clave) < 0)
		return obtener_puntero_abb_nodo(arbol, clave, &(*nodo)->der);

	// La clave es mayor, segun el comparador, que el (*nodo)->clave.
	return obtener_puntero_abb_nodo(arbol, clave, &(*nodo)->izq);
}

bool abb_guardar(abb_t *arbol, const char *clave, void *dato){
	abb_nodo_t **elemento = obtener_puntero_abb_nodo(arbol, clave, &arbol->raiz);
	// La clave esta en el abb.
	if ((*elemento) != NULL){
		if(arbol->destruir_dato != NULL)
			arbol->destruir_dato((*elemento)->dato);
		// Se asigna el nuevo dato al elemento.
		(*elemento)->dato = dato;
		return true;
	}

	// La clave no existe en el abb.
	abb_nodo_t *abb_nodo = abb_nodo_crear(clave, dato);
	if (!abb_nodo)
		return false;
	*elemento = abb_nodo;

	// Hay un elemento mas en el abb.
	arbol->cantidad += 1;
	return true;
}

void* abb_obtener(const abb_t* arbol, const char* clave){
	abb_nodo_t **nodo = obtener_puntero_abb_nodo(arbol , clave, &arbol->raiz);
	// La clave no existe en el abb.
	if(*nodo == NULL)
		return NULL;
	// La clave esta en el abb.
	return (*nodo)->dato;
}

bool abb_pertenece(const abb_t* arbol, const char* clave){
	abb_nodo_t **nodo = obtener_puntero_abb_nodo(arbol , clave, &arbol->raiz);
	return (*nodo) != NULL;
}

// Devuelve el nodo que reemplazara al nodo que contiene la clave a borrar.
// Pre: el nodo fue creado.
abb_nodo_t *obtener_nodo_reemplazar(abb_nodo_t *nodo){
	if (nodo->der == NULL)
		return nodo;

	abb_nodo_t *nodo_buscado = obtener_nodo_reemplazar(nodo->der);
	// Se asigna al padre del nodo bucado, el nodo izq o NULL del nodo buscado.
	if (nodo->der == nodo_buscado)
		nodo->der = nodo_buscado->izq;

	return nodo_buscado;
}

void* abb_borrar(abb_t* arbol, const char* clave){
	abb_nodo_t **nodo = obtener_puntero_abb_nodo(arbol , clave, &arbol->raiz);
	abb_nodo_t *nodo_aux = NULL;

	// La clave no existe en el abb.
	if(*nodo == NULL)
		return NULL;

	// 3er Caso: dos nodos hijos. O 2do Caso: un nodo hijo izq no nulo.
	if( (*nodo)->izq != NULL){
		nodo_aux = obtener_nodo_reemplazar((*nodo)->izq);
		// En el caso que el nodo der de (*nodo)->izq sea NULL no se debe modificar su nodo izq.
		if (nodo_aux != (*nodo)->izq)
			nodo_aux->izq = (*nodo)->izq;
		nodo_aux->der = (*nodo)->der;
	}
	// 2do Caso: un nodo hijo der no nulo.
	if((*nodo)->izq == NULL && (*nodo)->der != NULL)
		nodo_aux = (*nodo)->der;

	// 1er Caso: nodo hoja(no tiene nodos hijos).
	// Coincide con la destruccion del nodo y el intercambio de puntero del 2do y 3er caso.
	void *dato = (*nodo)->dato;

	abb_nodo_destruir((*nodo), NULL);
	*nodo = nodo_aux;

	// Hay un elemento menos en el abb.
	arbol->cantidad-=1;
	return dato;
}

size_t abb_cantidad(abb_t *arbol){
	return arbol->cantidad;
}

// Destruye todos los nodos del arbol.
// Pre: el arbol fue creado.
// Post: se libero toda la memoria ocupada por los nodos del arbol. No devuelve nada.
void abb_destruir_nodos(abb_nodo_t *nodo, abb_destruir_dato_t destruir_dato){
	if (!nodo)
		return;

	abb_destruir_nodos(nodo->der, destruir_dato);
	abb_destruir_nodos(nodo->izq, destruir_dato);

	abb_nodo_destruir(nodo, destruir_dato);
}

void abb_destruir(abb_t *arbol){
	abb_destruir_nodos(arbol->raiz, arbol->destruir_dato);
	free(arbol);
}


/*******************************************************************
 *              IMPLEMENTACION PRIMITIVAS DE ITERACION
 ******************************************************************/

abb_iter_t* abb_iter_in_crear(const abb_t* arbol){
	abb_iter_t* iter = malloc(sizeof(abb_iter_t));
	if(!iter)
		return NULL;

	iter->pila = pila_crear();
	if(!iter->pila){
		free(iter);
		return NULL;
	}

	iter->arbol = arbol;
	if(!arbol->raiz){
		iter->actual = NULL;
		return iter;
	}

	abb_nodo_t* nodo_aux = arbol->raiz;
	pila_apilar(iter->pila, nodo_aux);

	nodo_aux = pila_ver_tope(iter->pila);
	// Se apilan todos los nodos derechos posibles.
	while(nodo_aux->der){
		pila_apilar(iter->pila, nodo_aux->der);
		nodo_aux = nodo_aux->der;
	}
	iter->actual = pila_ver_tope(iter->pila);
	return iter;
}

bool abb_iter_in_avanzar(abb_iter_t *iter){
	if (abb_iter_in_al_final(iter))
		return false;

	abb_nodo_t *elemento = pila_desapilar(iter->pila);
	if (elemento->izq){
		// Se apila el nodo izquierdo del desapilado.
		pila_apilar(iter->pila, elemento->izq);
		elemento = elemento->izq;
		// Se apilan todos los nodos derechos posibles.
		while (elemento->der != NULL){
			pila_apilar(iter->pila, elemento->der);
			elemento = elemento->der;
		}
	}
	iter->actual = pila_ver_tope(iter->pila);
	return true;
}

// Aplica la funcion visitar a los elementos del arbol en inorden, utilizando la pila de recursion para
// repetar ese orden. Devuelve true si se quiere seguir avanzando, false en caso contrario.
// Pre: el nodo y la funcion visitar fueron creadas.
// Post: se aplico la funcion visitar a cada elemento del arbol hasta que se llego
// al final del mismo o cuando la funcion visitar devuelvio false.
bool _abb_in_order(abb_nodo_t *nodo, bool visitar(const char *, void *, void *), void *extra){
	bool seguir = true;
	if (!nodo)
		return true;
	seguir = _abb_in_order(nodo->der, visitar, extra);
	// Si alguna vez no se quizo seguir avanzando, no se aplicara la funcion visitar a los siguientes nodos,
	// y no se seguira avanzando.
	if (!seguir)
		return false;
	// Se devuleve false en la primer vez que no se quiera seguir avanzando.
	if (!visitar(nodo->clave, nodo->dato, extra))
		return false;
	_abb_in_order(nodo->izq, visitar, extra);
}

void abb_in_order(abb_t *arbol, bool visitar(const char *, void *, void *), void *extra){
	_abb_in_order(arbol->raiz, visitar, extra);
}

const char* abb_iter_in_ver_actual(const abb_iter_t* iter){
	if (iter == NULL || iter->actual == NULL)
		return NULL;
	return iter->actual->clave;
}

bool abb_iter_in_al_final(const abb_iter_t* iter){
	return pila_esta_vacia(iter->pila);
}

void abb_iter_in_destruir(abb_iter_t* iter){
	pila_destruir(iter->pila);
	free(iter);
}
